﻿/**
*@author yuruiqiao
*@date 2020-3-9
*@function of SeqList
*/
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
# include <string.h>
//初始化顺序表的长度是50
#define initSize 50
#define true 1
#define false 0
//布尔类型
typedef int bool;
//定义表的value类型
typedef int ElemType;
//这边用于表示顺序表
typedef struct {
	ElemType *data;
	int length,maxSize;
} SeqList;

//这边用于初始化一个空顺序表
SeqList* initSeqList() {
	SeqList* seqList = (SeqList*)malloc(sizeof(SeqList));
	seqList->data = (ElemType*)malloc(sizeof(ElemType) * initSize);
	seqList->length = 0;
	seqList->maxSize = initSize;
	return seqList;
}

//自定义顺序表
void customizeList(SeqList* seqList,ElemType* data,int size) {
	for (int i = 0;i<size;i++) {
		seqList->data[i] = data[i];
		seqList->length++;
	}
}

//随机生成长度为num的顺序表
void RandList(SeqList* seqList,int num) {
	srand((unsigned)time(NULL));
	for (int i = 0; i <num; i++){
		seqList->data[i] = rand() % 10;
		seqList->length++;
	}
}

//随机生成长度为num的有序表(降序)
void DescRandList(SeqList* seqList, int num) {
	srand((unsigned)time(0));
	for (int i = num-1; i >= 0; i--) {
		seqList->data[num-i-1] = i -(rand() % 10)/5;
		if (seqList->data[num - i - 1] < 0) {
			seqList->data[num - i - 1] = 0;
		}
		seqList->length++;
	}
}

//随机生成长度为num的有序表(升序)
void AscRandList(SeqList* seqList, int num) {
	srand((unsigned)time(0));
	for (int i = 0; i < num; i++) {
		seqList->data[i] = i + (rand() % 10) / 5;
		seqList->length++;
	}
}

//求表长度
int Length(SeqList* seqList) {
	return seqList->length;
}
//按照值查找
int LocateElem(SeqList* seqList, ElemType e) {
	for (int i = 0; i < seqList->length; i++){
		if (seqList->data[i]== e) {
			return i+1;
		}
	}
	return -1;
}

//获取第i个元素
ElemType GetElem(SeqList* seqList, int i) {
	if (i<1||i>seqList->length) {
		return -1;
	}
	return seqList->data[i-1];
}

//插入操作
bool ListInsert(SeqList* seqList, int index, ElemType e) {
	//和数组不同,插入操作的序号从1开始,n+1结束,因为n+1相当于尾插入
	if (index<1|| index > seqList->length+1) {
		return false;
	}
	for (int i = seqList->length;i > index;i--) {
		seqList->data[i]= seqList->data[i-1];
	}
	seqList->data[index-1] = e;
	seqList->length++;
	return  true;
}
//删除操作
bool ListDelete(SeqList* seqList, int index, ElemType* e) {
	//和数组不同,删除操作的序号从1开始,n结束
	if (index<1 || index > seqList->length) {
		return false;
	}
	//用于存储被删除的元素
	*e = seqList->data[index-1];
	for (int i = index;i < seqList->length;i++) {
		seqList->data[i-1] = seqList->data[i];
	}
	seqList->length--;
	return  true;
}
//打印操作
void PrintList(SeqList* seqList) {
	if (seqList == NULL) {
		printf("NULL\n");
		return;
	}
	if (seqList->length==0) {
		printf("list:()\n");
		return;
	}
	printf("list:(");
	for (int i = 0; i < seqList->length-1; i++){
		printf("%d,", seqList->data[i]);
	}
	printf("%d)\n", seqList->data[seqList->length - 1]);
}
//判断是否为空
bool isEmpty(SeqList* seqList) {
	return seqList->length==0;
}
//销毁操作,后面的二级指针用于将野指针指向空
bool DestroyList(SeqList* seqList, SeqList** plist) {
	if (seqList == NULL) {
		return false;
	}
	free(seqList->data);
	seqList->data = NULL;
	free(seqList);
	*plist = NULL;
	return true;
}

//两个有序表合成一个新的有序表(时间复杂度O(2n))
SeqList* compose(SeqList* A, SeqList* B) {
	if (A->length + B->length > initSize)
		return A;
	SeqList* newList = initSeqList();
	int i, j,k=0;
	int rank1, rank2;
	//用于判断升序和降序
	rank1 = A->data[A->length - 1] - A->data[0];
	rank2 = B->data[B->length - 1] - B->data[0];
	i = rank1 < 0 ? A->length - 1 : 0;
	j = rank2 < 0 ? B->length - 1 : 0;
	//定义和i,j比较的数
	int status1 = (i == 0) ? A->length  : -1;
	int status2 = (j == 0) ? B->length  : -1;
	//一直插入最小的元素,直到其中一个表遍历完毕
	while (i* rank1 < status1* rank1&& j* rank2 < status2* rank2)
		if (A->data[i] <= B->data[j]) 
			newList->data[k++] = A->data[rank1 > 0 ? i++ : i--];
		else 
			newList->data[k++] = B->data[rank2 > 0 ? j++ : j--];
	//遍历剩下的一个表
	while (i * rank1 < status1 * rank1)
		newList->data[k++] = A->data[rank1 > 0 ? i++ : i--];
	while (j* rank2 < status2* rank2)
		newList->data[k++] = B->data[rank2 > 0 ? j++ : j--];
	newList->length = A->length + B->length;
	return newList;
}

//有序表中查找x,找到则将x与后一个元素互换,否则插入x使顺序表仍然有序,查找效率O(logn)
void search(SeqList* seqList,ElemType x) {
	//尾插入或者x就是最后一个元素
	if (x>=seqList->data[seqList->length - 1]) {
		seqList->data[seqList->length];
		seqList->length++;
		return;
	}
	//头插入或者x就是第一个元素
	if (x <= seqList->data[0]) {
		for (int i = seqList->length;i >0;i--)
			seqList->data[i] = seqList->data[i - 1];
		seqList->data[0] = x;
		seqList->length++;
		return;
	}
	//x的值在中间范围
	int flag = seqList->length - 1;
	int distance = flag/2;
	while (distance > 0) {
		distance /= 2;
		if ( x == seqList->data[flag]) {
			seqList->data[flag] = seqList->data[flag + 1];
			seqList->data[flag+1] = x;
			return;
		}
		else if (x<seqList->data[flag])
			flag -= distance;
		else
			flag += distance;
	}
	flag = x < seqList->data[flag] ? flag : flag + 1;
	for (int i = seqList->length;i > flag;i --)
		seqList->data[i] = seqList->data[i - 1];
	seqList->data[flag] = x;
	seqList->length++;
}

//查找一个序列中数量大于序列长度一半的元素,要求空间复杂度O(1),时间复杂度尽可能小
ElemType findMode(SeqList* seqList) {
	int flag;
	int num = 0;
	//如果长度为奇数,则用2整除+1
	int maxNum = seqList->length%2==0 ? seqList->length / 2: seqList->length / 2 + 1;
	//如果num+未遍历数<maxNum,直接退出循环,平均外层遍历次数为n/2
	for (int i = 0;num + seqList->length - i >= maxNum && i < seqList->length; i++){
		flag = seqList->data[i];
		//遇到连续相同的数字,进行下一轮外层循环
		if (seqList->data[i + 1] == flag) {
			num++;
			continue;
		}
		//内层循环,平均内层遍历次数为n/2
		for (int j = i;num + seqList->length - j  >= maxNum && j < seqList->length;j++) {
			if (seqList->data[j] == flag)
				num++;
			if (num == maxNum)
				return seqList->data[j];
		}
		//内层循环结束清零
		num = 0;
	}
	return -1;
}

//找到最小的未出现的正整数,要求时间高效,采用空间换时间,原始做法,占用空间不合理
ElemType findMin(SeqList* seqList) {
	int max = 0;
	//找到最大的元素
	for (int i = 0;i < seqList->length;i++) {
		if (seqList->data[i] > max) {
			max = seqList->data[i];
		}
	}
	//分配最大元素大小的空间
	ElemType* temp = (ElemType*)malloc(sizeof(ElemType) * (max+1));
	memset(temp,0, sizeof(ElemType) * (max + 1));
	for (int i = 0;i < seqList->length;i++)
		if (seqList->data[i] > 0)
			temp[seqList->data[i]]++;
	//找到最小的非正数,返回下标
	for (int i = 1;i <= max;i++)
		if (temp[i] == 0) 
			return i;
	return max+1;
}
//算法的优化,优化思路:事实上不必要用最大值作为开辟空间的依据
//因为n+1就是返回值的最大值,即前n个数分别是1~n这时候未找到的最小的整数是n+1,否则必然小于n+1
ElemType findMissMin(SeqList* seqList,int n) {
	int i;
	ElemType* temp = (ElemType*)malloc(sizeof(ElemType) * n);
	memset(temp, 0, sizeof(ElemType) * n);
	//将找到的比较小的值依次放到temp中
	for (i = 0;i < n;i++)
		if (seqList->data[i] > 0&& seqList->data[i] <=n)
			temp[seqList->data[i]-1]=1;
	//找所有空出来的部分下标的最小值,没找到的话说明1~n都满了那最小未找到只能是n+1
	for (i = 0;i < n;i++)
		if (temp[i] == 0) break;
	return i + 1;
}
int main() {
	SeqList* list1 = initSeqList();
	ElemType value[9] = {1,4,3,3,3,3,5,3,1};
	customizeList(list1, value,9);
	PrintList(list1);
	ElemType result = findMissMin(list1,9);
	printf("%d\n", result);
	DestroyList(list1,&list1);
	PrintList(list1);
}